/**
 * Copyright 2007-2008 Alex Tkachman
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.ait.actors;

import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.atomic.AtomicLongFieldUpdater;
import java.util.concurrent.atomic.AtomicReferenceArray;

public class ConcurrentDeque<V> extends ReentrantLock implements StealableDeque<V> {
    private volatile CircularArray<V> data;
    private volatile long topSize;

    private final static AtomicLongFieldUpdater tsUpdater = AtomicLongFieldUpdater.newUpdater(ConcurrentDeque.class, "topSize");

    private static class CircularArray<V> extends AtomicReferenceArray<V> {
        public CircularArray(int length) {
            super(length);
        }

        public void setValue (int index, V value) {
            set (index & (length()-1), value);
        }

        public V getValue (int index) {
            return get (index & (length()-1));
        }

        public boolean compareAndSetValue(int index, V expected, V value) {
            return compareAndSet(index & (length()-1), expected, value);
        }
    }

    public ConcurrentDeque() {
        data = new CircularArray<V> (2);
        topSize = makeTopSize(0,0);
    }

    private long makeTopSize(int top, int size) {
        return (((long)top) << 32) + size;
    }

    private boolean resizeLast(CircularArray<V> d, long ts, V value) {
        lock ();
        try {
            if (data != d)
              return false;

            data = null;
            int size = d.length ();
            int t = (int)((ts >> 32));
            CircularArray<V> newData = new CircularArray<V> (2*size);
            for (int i = 0; i != size-1; ++i) {
                newData.setValue(t+i, d.getValue(t+i));
            }
            newData.setValue(t+size-1,value);

            topSize = makeTopSize(t,size);
            data = newData;
            return true;
        }
        finally {
            unlock();
        }
    }

    private boolean resizeFirst(CircularArray<V> d, long ts, V value) {
        lock ();
        try {
            if (data != d)
              return false;

            data = null;
            int size = d.length ();
            int t = (int)((ts >> 32));
            CircularArray<V> newData = new CircularArray<V> (2*size);
            for (int i = 0; i != size-1; ++i) {
                newData.setValue(t+i, d.getValue(t+i));
            }
            newData.setValue(t+size,value);

            t = t-1;
            if (t < 0) {
                t = newData.length()-1;
            }
            newData.setValue(t, value);

            topSize = makeTopSize(t,size);
            data = newData;
            return true;
        }
        finally {
            unlock();
        }
    }

    public void addLast(V value) {
        for (;;) {
            CircularArray<V> d = getData();
            long ts = topSize;
            int sz = (int)(ts & 0xFFFFFFFFL);
            int t = (int)((ts >> 32));
            if (sz == d.length()-1) {
                if (resizeLast(d, ts, value))
                  return;
            }
            else {
                long newTB = makeTopSize(t,sz+1);
                if (tsUpdater.compareAndSet(this,ts,newTB)) {
                    getData().setValue(t+sz, value);
                    break;
                }
            }
        }
    }

    public void addFirst(V value) {
        for (;;) {
            CircularArray<V> d = getData();
            long ts = topSize;
            int sz = (int)(ts & 0xFFFFFFFFL);
            int t = (int)((ts >> 32));
            if (sz == d.length()-1) {
                if (resizeFirst(d, ts, value))
                  return;
            }
            else {
                int newTop = t-1;
                if (newTop < 0) {
                  newTop += d.length();
                }
                long newTB = makeTopSize(newTop,sz+1);
                if (tsUpdater.compareAndSet(this,ts,newTB)) {
                    getData().setValue(newTop, value);
                    break;
                }
            }
        }
    }

    public V removeLast() {
        for (;;) {
            CircularArray<V> d = getData();
            long tb = topSize;
            int sz = (int)(tb & 0xFFFFFFFFL);
            int t = (int)((tb >> 32));
            if (sz == 0) {
                return null;
            }
            else {
                V res = d.getValue(t+sz-1);
                if (res != null) {
                    long newTB = makeTopSize(t,sz-1);
                    if (tsUpdater.compareAndSet(this,tb,newTB)) {
                        getData().compareAndSetValue(t+sz-1, res, null);
                        return res;
                    }
                }
            }
        }
    }

    public int getSize() {
        return (int)(topSize & 0xFFFFFFFFL);
    }

    public V removeFirst() {
        for (;;) {
            CircularArray<V> d = getData();
            long ts = topSize;
            int sz = (int)(ts & 0xFFFFFFFFL);
            int t = (int)((ts >> 32));
            if (sz == 0) {
                return null;
            }
            else {
                int newTop = t+1;
                if (newTop == d.length()) {
                    newTop = 0;
                }
                V res = d.getValue(t);
                if (res != null) {
                    long newTB = makeTopSize(newTop,sz-1);
                    if (tsUpdater.compareAndSet(this,ts,newTB)) {
                        getData().compareAndSetValue(t, res, null);
                        return res;
                    }
                }
            }
        }
    }

    private CircularArray<V> getData() {
      CircularArray<V> d = data;
      if (d == null) {
          lock ();
          try {
              return data;
          }
          finally {
              unlock();
          }
      }
      return d;
    }
}